package dp;
import java.util.*;
import java.io.*;
public class _13_kama_52_完全背包 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int n,m;
	static StringTokenizer st;
	static int N = 10010;
	static int w[] = new int[N];
	static int v[] = new int[N];
	static int dp[] = new int[N];
	public static void main(String[] args) throws IOException{
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());// 多少个物品
		m = Integer.parseInt(st.nextToken());// 总空间
		
		for(int i = 1; i <= n ; i++) {
			st = new StringTokenizer(br.readLine());
			w[i] = Integer.parseInt(st.nextToken());
			v[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(w[i] <= j) {
					dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
				}
			}
		}
		
		for(int i = 1; i <= m; i++) {
			System.out.print(dp[i] + " ");
		}
		
		System.out.println(dp[m]);
	}
}
